package com.lancer.algorithm.huawei;

import java.io.*;

public class Main015 {

    /**
     * 思想：将能整除3或者5的各自分为一组，记为sum1和sum2，剩余的保存在数组nums里
     * 现有两组，剩余nums里的数要么在sum1里要么在sum2里，利用递归依次放在sum1和sum2中
     * 最终nums里的数字全部放进去，若sum1 == sum2，则返回true，否则，返回false
     */

    /**
     *
     * @param args
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = "";
        while((line = br.readLine()) != null){
            // 数组长度
            int len = Integer.parseInt(line);
            line = br.readLine();
            String[] strInput = line.split(" ");
            int[] input = new int[len];
            for(int i=0; i<input.length; i++){
                input[i] = Integer.parseInt(strInput[i]);
            }
            System.out.println(calc(input));
        }
    }

    /**
     * 将能整除3或者5的各自分为一组，记为s1和s2，剩余的保存在数组other里
     * @param input
     * @return
     */
    static boolean calc(int[] input){
        // sum1-5的倍数数字之和，sum2-3的倍数数字之和，j其他数字数组的指针
        int sum1 = 0, sum2 = 0, j = 0;
        // 存储其他数字的数组
        int[] other = new int[input.length];
        for(int i=0; i<input.length; i++){
            if(input[i] % 5 == 0) {
                sum1 += input[i];
            }else if (input[i] % 3 == 0) {
                sum2 += input[i];
            } else {
                other[j++] = input[i];
            }
        }
        return calc_recur(sum1, sum2, other, j, 0);
    }

    /**
     * 递归穷举其他数组放在s1或者s2中的可能性，得出结论
     * @param s1  5的倍数数字之和
     * @param s2 3的倍数数字之和
     * @param other  其他数字的数组
     * @param maxIdx  其他数字个数
     * @param idx  其他数字已经放到s1或者s2中的个数，初始为0，递归一次就+1，最终和其他数字总个数相同时，说明已经放完
     * @return
     */
    static boolean calc_recur(int s1, int s2, int[] other, int maxIdx, int idx){
        if(idx == maxIdx){//
            return s1 == s2;
        } else {
            // 分别试着将其他数字放在s1或者s2中，
            // 穷举所有可能性，只要有一个返回true，则整体结果为true
            return calc_recur(s1 + other[idx], s2, other, maxIdx, idx+1) || calc_recur(s1, s2 + other[idx], other, maxIdx, idx+1);
        }
    }

}
